Networks of computer systems may be made of interconnected autonomous systems. Each autonomous system (AS) contains communication equipment such as conventional routers that can send and receive traffic. Traffic may be sent to, or received from, internal networks of computer systems operated by parties who have contracted with the operator of the AS for service, or to or from other autonomous systems. An operator of an AS may be a conventional Internet service provider or another entity. Each AS is assigned one or more blocks of addresses that they can optionally divide and assign to internal networks of that AS.
Traffic sent to or received from remote autonomous systems is sent and received via border routers at the edge of each autonomous system. To allow each autonomous system to identify which remote autonomous system can forward traffic to a particular network destination, the border routers of each autonomous system periodically provide, to the border routers of each autonomous system to which they are directly connected, information about the addresses of each network destination for which they can handle traffic. Because the addresses will usually include a large number of addresses, blocks of addresses are each described as a range of addresses by specifying an address and mask pair. A network address is in the range if the address, logically ANDed with the mask matches the address in the pair. The border routers in each receiving AS receive this information and provide this information to the other devices in the same AS as the receiving AS or transmit it to a route reflector, which forwards the information to the other routers in the same AS as the receiving AS.
More than one border router may thus advertise that it can reach a same network destination advertised by another border router. The other routers in the AS choose, from among those border routers that advertise that they can reach a network destination, using various parameters, including the cost metrics assigned to the links in the shortest path to each such border router. If the combination of other parameters used to select a border router are the same, the border router having the shortest least cost path will be selected.
The communication equipment in each AS uses the information it receives from other autonomous systems as well as information about the internal networks of that autonomous system to build one or more routing tables to identify the optimal route within the AS for every network destination. When the communication equipment of an AS receives a communication to be forwarded, it compares the destination address in the header of the communication with the entries in the routing tables. The routing tables for a piece of communication equipment tell that piece of communication equipment how to forward the communication to the next piece of communication equipment in the direction of the optimal path.
However, there is a problem with this approach. Although there may be several border routers capable of reaching a network destination, traffic arriving at an ingress point of an AS and having a certain destination will always take the same path through an AS to reach that destination. In some cases, multiple ingress points on a network will funnel traffic through the same egress point of the network to reach a set of external networks. This is because the routes are selected without regard for the amount of traffic flowing over a particular path. A point of origin that receives a large amount of traffic may forward that traffic via the same path to the destination, potentially saturating the least cost path while another path that could have been used sits relatively idle.
This problem is particularly troublesome in the case of traffic forwarded to a remote AS. There are often many border routers of the AS that could be used to forward the traffic from the AS to the remote AS, but the communication equipment uses the techniques described above and therefore an ingress router will always forward any traffic it receives to the same border router serving the remote AS. While the network costs may be adjusted to allow traffic received at different points of origin on the AS to take different paths, adjusting the network costs can be difficult to implement without adversely affecting other traffic, and there is still no effective solution when the bulk of the traffic to a destination is received at one point of origin. Because of the large installed base of network communication equipment, any solution to this problem must be compatible with such existing network communication equipment. What is needed is a system and method that can cause traffic received by one AS having a destination in another AS to take different paths, even if it is received at the same point of origin, and in a manner that is compatible with existing network communication equipment.